package edu.whu.rose.clock.kps.algorithm.blinks.search3;

import java.io.UnsupportedEncodingException;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import com.sleepycat.je.DatabaseException;

import edu.whu.rose.clock.kps.algorithm.blinks.index.BilevelIndexDB;
import edu.whu.rose.clock.kps.algorithm.blinks.index.BlockKeyword;
import edu.whu.rose.clock.kps.algorithm.blinks.index.BlockVertexKeyword;
import edu.whu.rose.clock.kps.algorithm.blinks.index.KNEntry;
import edu.whu.rose.clock.kps.algorithm.blinks.index.NKEntry;
import edu.whu.rose.clock.kps.algorithm.blinks.index.PNEntry;
import edu.whu.rose.clock.kps.algorithm.blinks.search2.BiLevelSearch2;
import edu.whu.rose.clock.kps.datastruct.SimpleAnswer;
import edu.whu.rose.clock.kps.datastruct.SimpleSubgraphVertex;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.MyMath;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;

public class BiLevelSearch3 {

	private BilevelIndexDB bidb;
	
	private double bound;
	
	public long totalTime;
	public long indexTime;
	
	private String[] keywords;
	
	private HashMap<BlockKeyword, KNEntry[]> knentries;
	private HashMap<SimpleSubgraphVertex, PNEntry[]> pnentries;
	
	private HashMap<Integer, PotentialTree3> trees;
	private HashMap<Integer, int[]> allPredecessors;
	
	public BiLevelSearch3(BilevelIndexDB bidb) {
		this.bidb = bidb;
	}
	
	public static void main(String[] args) {
		BilevelIndexDB bidb = new BilevelIndexDB();
		if (bidb.initEnv() && bidb.openDB()) {
			BiLevelSearch2 blinks = new BiLevelSearch2(bidb);
			String[] keywords = new String[]{"schema", "reuse"};
			int k = 100;
			
			for (int w = 0; w < 5; w++) {
				blinks.indexTime = 0l;
				SimpleAnswer[] answers = blinks.process(keywords, k);
				
				
				if (answers != null) {
					double sum = 0.0d;
					int i = 0;
					for (; i < answers.length; i++) {
						SimpleAnswer sa = answers[i];
						System.out.print("Rank " + (i + 1) + ": {" + sa.getScore() + "} ");
						System.out.print(" root[" + sa.getRoot() + "] ");
						sum += sa.getScore();
						for (int y = 0; y < sa.getLeafNumber(); y++) {
							int[] path = sa.getPath(y);
							System.out.print("( ");
							if (path != null) {
								for (int m = 0; m < path.length; m++) {
									System.out.print(path[m] + ", ");
								}
							}
							System.out.print(" )");
						}
						System.out.println();
					}
					if (i == 0) {
						System.out.println("Sorry, no result is found.");
					}
					else {
						System.out.println("Average score: " + (sum / Math.min(k, i)));
					}

					System.out.println("Time exhausted for reading index: " + blinks.indexTime + "ms");
					System.out.println("Time exhausted for searching: " + blinks.totalTime + " ms");
				}
				else {
					System.out.println("Sorry, no result is found.");
				}
			}
			
			bidb.closeDB();
		}
	}
	
	public SimpleAnswer[] process(String[] keywords, int k) {
		Date startTime = new Date();
		
		this.keywords = keywords;
		
		SimpleAnswer[] topk = new SimpleAnswer[k];
		int size = 0;
		
		knentries = new HashMap<BlockKeyword, KNEntry[]>();
		pnentries = new HashMap<SimpleSubgraphVertex, PNEntry[]>();
		
		trees = new HashMap<Integer, PotentialTree3>();
		allPredecessors = new HashMap<Integer, int[]>();

		GroupHeap3[] heaps = new GroupHeap3[keywords.length];
		
		ArrayList<HashSet<Integer>> crossed = new ArrayList<HashSet<Integer>>();
		for (int i = 0; i < keywords.length; i++) {
			crossed.add(new HashSet<Integer>());
		}
		
		HashSet<Integer> abandoned = new HashSet<Integer>();
		
		int visitTime = 0;
		int repeatTime = 0;
		
		bound = Double.MAX_VALUE;
		boolean overBound = false;
		
		boolean first_k = true;
		
		Date date = null;
		
		// initialize heaps
		for (int i = 0; i < keywords.length; i++) {
			heaps[i] = new GroupHeap3();
			date = new Date();
			int[] blockIds = null;
			try {
				blockIds = bidb.getFromKeywordBlock(keywords[i]);
			}
			catch (DatabaseException ex) {
				ex.printStackTrace();
			}
			catch (UnsupportedEncodingException ex) {
				ex.printStackTrace();
			}
			indexTime += new Date().getTime() - date.getTime();
			for (int j = 0; j < blockIds.length; j++) {
				BlockKeyword bk = new BlockKeyword(blockIds[j], keywords[i]);
				KNEntry[] list = null;
				date = new Date();
				try {
					list = bidb.getFromKeywordVertex(bk);
					if (list == null) {
						System.err.println("Error: cannot find KN list for block #" + 
								blockIds[j] + " and keyword: " + keywords[i]);
						System.exit(1);
					}
				}
				catch (DatabaseException ex) {
					ex.printStackTrace();
				}
				indexTime += new Date().getTime() - date.getTime();
				KNCursor3 knc = new KNCursor3(blockIds[j], list);
				knentries.put(bk, list);
				heaps[i].enqueue(knc);
			}
		}
		
		try {
			while (true) {
				// expand group by group
				for (int i = 0; i < keywords.length; i++) {
					visitTime++;
					
					Cursor3 cursor = heaps[i].dequeue();
					cursor.next();

					int block = cursor.getBlock();
					double distance = cursor.getDistance();
					int vertex = cursor.getNode();
					int first = cursor.getFirst();
					
					Integer Root = new Integer(vertex);
					
					// put the cursor back to heap if it is not empty
					if (!cursor.empty()) {
						heaps[i].enqueue(cursor);
					}
					
					// maintaining predecessor records, which is always necessary
					int[] predecessors = allPredecessors.get(Root);
					if (predecessors == null) {
						predecessors = new int[keywords.length];
						predecessors[i] = first;
						allPredecessors.put(Root, predecessors);
					}
					else {
						if (predecessors[i] == 0) {
							predecessors[i] = first;
						}
						else {
							repeatTime++;
						}
					}

					// do not visit this root if it has been abandoned
					if (abandoned.contains(Root)) {
						continue;
					}
					
					// visit current root
					boolean mark = true;
					PotentialTree3 tree = trees.get(Root);

//					if (vertex == 115426) {
//						System.out.println();
//					}

					// the tree does not exist
					// produce a new tree at this root, and try forward connection to other group in this block
					if (tree == null) {
						tree = new PotentialTree3(keywords.length);
						tree.setDistance(i, distance);
						// try to look forward
						date = new Date();
						double np = bidb.getFromVertexPortal(new SimpleSubgraphVertex(block, vertex));
						indexTime += new Date().getTime() - date.getTime();
						if (np == 0.0d) { // this vertex is a portal
							// get all blocks it resides on
							date = new Date();
							int[] blocks = bidb.getFromPortalBlock(vertex);
							indexTime += new Date().getTime() - date.getTime();
							
							for (int j = 0; j < keywords.length; j++) {
								if (j != i) {
									double minNK = Double.MAX_VALUE;
									for (int n = 0; n < blocks.length; n++) {
										double nk = 0.0d;
										NKEntry nke = null;
										try {
											date = new Date();
											nke = bidb.getFromVertexKeyword(new BlockVertexKeyword(blocks[n], vertex, keywords[j]));
											indexTime += new Date().getTime() - date.getTime();
											if (nke != null) {
												nk = nke.getDistance();
												if (nk < minNK) { // a new shortest path from root to keywords[j] is found
													minNK = nk;
													tree.setDistance(j, nk);
													predecessors[j] = nke.getFirst();
													tree.setOriginBlock(blocks[n]);
//													tree.setD2(j, nk);
												}
												else {
													tree.setD2(j, np);
												}
											}
										}
										catch (DatabaseException ex) {
											ex.printStackTrace();
										}
									}
								}
							}
						}
						else {
							for (int j = 0; j < keywords.length; j++) {
								if (j != i) {
									double nk = 0.0d;
									NKEntry nke = null;
									try {
										date = new Date();
										nke = bidb.getFromVertexKeyword(new BlockVertexKeyword(block, vertex, keywords[j]));
										indexTime += new Date().getTime() - date.getTime();
										if (nke != null) {
											nk = nke.getDistance();
											if (np >= nk) { // the shortest path from root to keywords[j] is found
												tree.setDistance(j, nk);
												predecessors[j] = nke.getFirst();
												tree.setOriginBlock(block);
												tree.setD2(j, nk);
											}
											else {
												tree.setD2(j, np);
											}
										}
									}
									catch (DatabaseException ex) {
										ex.printStackTrace();
									}
								}
							}
						}
						
						
						trees.put(Root, tree); // put the tree into the forest
					}
					// the tree exists, but is over large and so will be abandoned
					else if (bound < Double.MAX_VALUE && sumLBD(tree, heaps, block, keywords) >= bound) {
						// abandon the tree
						abandoned.add(Root);
						trees.remove(Root);
						mark = false;
					}
					// the tree exists and is not over large, and has not been visited by this group
					else if (tree.getDistance(i) == Double.MAX_VALUE) {
						// update the shortest path from this root to keywords[i]
						tree.setDistance(i, distance);
					}
					// the tree exists and is not over large, but has been visited by this group
					else {
						// do nothing
						mark = false;
					}

					if (mark) { // the tree has been inserted or modified
						if (tree.isAnswer()) { // the tree is a new answer
							if (size < k || tree.sumDistances() < topk[k - 1].getScore()) {
								
//								if (vertex == 113607) {
//									System.out.println();
//								}
								
								SimpleAnswer newAnswer = convert(vertex, tree); // convert the tree to answer
								size = addTopKAnswer(newAnswer, topk, size); // add the answer to top-k
							}
							
							// abandon the tree, since we only allow single tree rooted at this vertex
							abandoned.add(Root);
							trees.remove(Root);

							if (size == k) {
								if (first_k) { // this is the first time we have k answers
									Date firstk = new Date();
//									System.out.println("Time exhausted for reading index: " + indexTime + "ms");
									System.out.println(
											"Time exhausted for producing first k answers: " + 
											(firstk.getTime() - startTime.getTime() - indexTime) + "ms");
									double sum = 0.0d;
									for (int n = 0; n < topk.length; n++) {
										SimpleAnswer sa = topk[n];
										System.out.print("Rank " + (n + 1) + ": {" + sa.getScore() + "} ");
										System.out.print(" root[" + sa.getRoot() + "] ");
										sum += sa.getScore();
										for (int y = 0; y < sa.getLeafNumber(); y++) {
											int[] path = sa.getPath(y);
											System.out.print("( ");
											if (path != null) {
												for (int m = 0; m < path.length; m++) {
													System.out.print(path[m] + ", ");
												}
											}
											System.out.print(" )");
										}
										System.out.println();
									}
									System.out.println("Average score: " + (sum / k));
									first_k = false;
								}
								bound = topk[k - 1].getScore();
							}
						}
					}
					
					// process for crossing blocks
					if (!crossed.get(i).contains(Root)) { // this root has not been crossed as a portal
						date = new Date();
						int[] PBList = bidb.getFromPortalBlock(vertex);
						indexTime += new Date().getTime() - date.getTime();
						if (PBList != null) { // this root is indeed a portal
							crossed.get(i).add(Root); // mark that it is crossed
							if (distance != 0.0d) { // if this root is not a matched vertex
								for (int j = 0; j < PBList.length; j++) { // for each block this portal connects
									int ablock = PBList[j];
									if (ablock != block) { // if the block is not current block
										SimpleSubgraphVertex bk = new SimpleSubgraphVertex(block, vertex);
										PNEntry[] list = pnentries.get(bk);
										if (list == null) {
											date = new Date();
											try {
												list = bidb.getFromPortalVertex(bk);
												if (list == null) {
													System.err.println("Error: cannot find PN list for block #" + 
															block + " and portal #" + vertex);
													System.exit(1);
												}
											}
											catch (DatabaseException ex) {
												ex.printStackTrace();
											}
											indexTime += new Date().getTime() - date.getTime();
											pnentries.put(bk, list);
										}
										PNCursor3 pnc = new PNCursor3(ablock, vertex, distance, list);
										if (!pnc.empty()) {
											heaps[i].enqueue(pnc); // add a new PN cursor
										}
									}
								}
							}
						}
					}
					
					// check if algorithm can be stopped
					if (size < k) {
						continue;
					}
					
					// condition 1: trees rooted at never-visited vertexes are all larger than the bound
					if (!overBound) {
						double total = 0.0d;
						for (int j = 0; j < keywords.length; j++) {
							double top = heaps[j].top();
							if (top != -1.0d) {
								total += top;
							}
						}
						if (total >= bound) {
							overBound = true;
						}
					}
					
					if (overBound) {
						// condition 2: trees rooted at already-visited vertexes have 
						// lower bounds larger than the bound
						Iterator<Integer> it = trees.keySet().iterator();
						while (it.hasNext()) {
							Integer root = it.next();
							PotentialTree3 pt = trees.get(root);
							if (sumLBD(pt, heaps, block, keywords) < bound) {
//								break;
							}
							else {
								abandoned.add(root);
								it.remove();
							}
						}
						if (trees.size() > 0) {
							continue;
						}
	
						// stopping the algorithm
						Date endTime = new Date();
						totalTime = endTime.getTime() - startTime.getTime() - indexTime;
						
						return topk;
					}
				}
			}
		}
		catch (DatabaseException ex) {
			ex.printStackTrace();
		}
		
		// finish all
		Date endTime = new Date();
		totalTime = endTime.getTime() - startTime.getTime() - indexTime;
		
		return topk;
	}
	
	private SimpleAnswer convert(int root, PotentialTree3 pt) {
		if (root == 173882) {
			System.out.println();
		}
		
		int[] leaves = new int[pt.size()];
		int[][] paths = new int[pt.size()][];
		SequentialIntArray allVertexes = new SequentialIntArray();
		allVertexes.insert(root);
		
		for (int i = 0; i < pt.size(); i++) {
			paths[i] = getPath(i, root, pt, allVertexes);
			if (paths[i] == null) {
				leaves[i] = root;
			}
			else {
				leaves[i] = paths[i][paths[i].length - 1];
			}
		}
		
		return new SimpleAnswer(root, leaves, paths, allVertexes.getArray());
	}
	
	private int[] getPath(int i, int root, PotentialTree3 pt,
			SequentialIntArray allVertexes) {
		ExpandableIntArray eia = new ExpandableIntArray();
		int current = root;

//		if (block == 0) {
//			System.out.println();
//		}
		
		
		while (current != -1) {
			int first = 0;
			int [] predecessors = allPredecessors.get(current);
			if (predecessors == null) {
				break;
			}
			first = predecessors[i];

//			if (first == 115426 && i == 0) {
//				System.out.println();
//			}
			
			if (first == 0) {
				break;
			}
			else if (first != -1) {
				allVertexes.insert(first);
				eia.add(first);
				current = first;
			}
			else {
				return eia.toArray();
			}
		}

		int block = pt.getOriginBlock();
		
		KNEntry[] list = knentries.get(new BlockKeyword(block, keywords[i]));
		for (int j = list.length - 1; j >= 0; j--) {
			if (list[j].getNode() == current) {
				current = list[j].getFirst();
				
				if (current == -1) {
					return eia.toArray();
				}
				else {
					eia.add(current);
					allVertexes.insert(current);
				}
			}
		}
		
		System.err.println("Error: path from " + current + " to group " + i + " not found");
		
		return eia.toArray();
	}
	
	private double sumLBD(PotentialTree3 tree, GroupHeap3[] heaps, int block, String[] keywords) {
		double sum = 0.0d;
		for (int i = 0; i < tree.size(); i++) {
			double distance = tree.getDistance(i);
			if (distance < Double.MAX_VALUE) {
				sum += distance;
			}
			else {
				double d1 = 0.0d;
				if (!heaps[i].isEmpty()) {
					d1 = heaps[i].top();
				}
				else {
					return Double.MAX_VALUE;
				}
				double d2 = tree.getD2(i);
				double d = Math.max(d1, d2);
				sum += d;
			}
		}
		return sum;
	}

	private int addTopKAnswer(SimpleAnswer answer, SimpleAnswer[] topk, int size) {
		int pos = -1;
		boolean inserted = false;
		for (int i = 0; i < size; i++) {
			int x = answer.compare(topk[i]);
			if (x == MyMath.ARR1_CONTAIN_ARR2) {
				return size;
			}
			else if (x == MyMath.ARR2_CONTAIN_ARR1) {
				if (!inserted) {
					for (int j = i; j > pos + 1; j--) {
						topk[j] = topk[j - 1];
					}
					topk[pos + 1] = answer;
					inserted = true;
				}
				else {
					for (int j = i; j < size - 1; j++) {
						topk[j] = topk[j + 1];
					}
					size--;
				}
			}
			else if (x == MyMath.ARR1_EQUAL_ARR2) {
				if (answer.getScore() < topk[i].getScore()) {
					for (int j = i; j > pos + 1; j--) {
						topk[j] = topk[j - 1];
					}
					topk[pos + 1] = answer;
					return size;
				}
				else {
					return size;
				}
			}
			
			if (answer.getScore() >= topk[i].getScore()) {
				pos = i;
			}
		}
		
		if (inserted) {
			return size;
		}
		
		if (pos < size - 1) {
			if (size < topk.length) {
				for (int i = size; i > pos + 1; i--) {
					topk[i] = topk[i - 1];
				}
				size++;
			}
			else {
				for (int i = topk.length - 1; i > pos + 1; i--) {
					topk[i] = topk[i - 1];
				}
			}
			topk[pos + 1] = answer;
		}
		else if (size < topk.length) {
			topk[size] = answer;
			size++;
		}
		
		return size;
	}

}
